<!DOCTYPE html>
<html>
	<head>
		<meta charset="UTF-8">
		<title></title>
	</head>
	<body>
		<!--基数排序 vs 计数排序 vs 桶排序
              这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
              基数排序：根据键值的每位数字来分配桶 计数排序：每个桶只存储单一键值 桶排序：每个桶存储一定范围的数值-->
		
		<!--桶排序
		解析:
			假设输入数据服从均匀分布，
			将数据分到有限数量的桶里，每个桶再分别排序
			（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排-->
		<script type="text/javascript">
			function bucketSort(array, num) {
				if (array.length <= 1) {return array;}
				var len = array.length,buckets = [],resule = [],
					min = max = array[0], regex = '/^[1-9]+[0-9]*$/',space,n = 0;
					num = num || ((num > 1 && regex.test(num)) ? num : 10);
				for (var i = 0; i < len; i++) {
					min = min <= array[i] ? min : array[i];
					max = max >= array[i] ? max : array[i];
				}
				space = (max - min + 1) / num;
				for (var j = 0; j < len; j++) {
					var index = Math.floor((array[j] - min) / space);
					if (buckets[index]) { // 非空桶，插入排序
						var k = buckets[index].length - 1;
						while(k >= 0 && buckets[index][k] > array[j]) {
							buckets[index][k + 1] = buckets[index][k];
							k--;
						}
						buckets[index][k + 1] = array[j];
					} else{ // 空桶，初始化
						buckets[index] = [];
						buckets[index].push(array[j]);
					}
				}
				while(n < num) {
					resule = resule.concat(buckets[n]);
					n++;
				}
				return resule;
			}
			var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
			document.write(bucketSort(arr, 4));
		</script>
	</body>
</html>
